package 测试2;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

/**
 * 1.将字符串转为字符数组，遍历统计每个字符出现的次数，放入hash表中
 * 
 * 2.创建节点TreeNode，放入一个优先队列
 * 
 * 3.构建哈夫曼树合并两个权重最小的节点，直到只剩下根节点root
 * 
 * 4.带着深度遍历树，计算长度和
 * 
 * @author hest0
 *
 */
class TreeNode {
	int weight;
	Character ch;
	TreeNode left;
	TreeNode right;

	public TreeNode(int weight) {
		this.weight = weight;
	}

	public TreeNode(int weight, Character ch) {
		this.weight = weight;
		this.ch = ch;
	}
}

public class 霍夫曼编码1 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String s = sc.nextLine();
			int result = hafuman(s);
			System.out.println(result);
		}
		sc.close();
	}

	public static int hafuman(String s) {
		char[] chars = s.toCharArray();

		// hash表存放每个字符和出现的次数
		HashMap<Character, Integer> hm = new HashMap<>();
		for (int i = 0; i < chars.length; i++) {
			if (hm.containsKey(chars[i])) {
				hm.put(chars[i], hm.get(chars[i]) + 1);
			} else {
				hm.put(chars[i], 1);
			}
		}

		// 优先队列（最小推），每次能得到weigh最小的node
		Queue<TreeNode> q = new PriorityQueue<>(hm.size(), new Comparator<TreeNode>() {
			@Override
			public int compare(TreeNode o1, TreeNode o2) {
				return Integer.compare(o1.weight, o2.weight);
			}
		});

		for (Map.Entry<Character, Integer> x : hm.entrySet()) {
			q.offer(new TreeNode(x.getValue(), x.getKey()));
		}

		while (q.size() > 1) {
			// 弹出两个最小的，合并为一个node
			TreeNode left = q.poll();
			TreeNode right = q.poll();
			TreeNode father = new TreeNode(left.weight + right.weight);

			father.left = left;
			father.right = right;
			q.offer(father);
		}
		TreeNode root = q.poll();
		// 计算长度
		return valLength(root, 0);
	}

	public static int valLength(TreeNode node, int depth) {
		if (node == null)
			return 0;// 仅计算ch有值的
		return (node.ch == null ? 0 : node.weight) * depth + valLength(node.left, depth + 1)
				+ valLength(node.right, depth + 1);
	}

}